from typing import List


def dfs(res, n, left, right, seq):

    if left == n and right == n:
        res.append(seq)
    else:
        if left < n:
            dfs(res, n, left + 1, right, seq + '(')
        if left > right and right < n:
            dfs(res, n, left, right + 1, seq + ')')


def generateParenthesis(n: int) -> List[str]:
    res = []
    dfs(res, n, 0, 0, '')
    return res


print(generateParenthesis(3))

